package main

/*
给定一个只包含三种字符的字符串：（，）和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 (必须有相应的右括号 )。
任何右括号 )必须有相应的左括号 (。
左括号 ( 必须在对应的右括号之前 )。
*可以被视为单个右括号 )，或单个左括号 (，或一个空字符串。
一个空字符串也被视为有效字符串。
*/
func main() {
	println(checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"))

}

/**
 *	checkValidString
 *	@Description: 栈
 *	@param s string
 *	@return bool
 */
func checkValidString(s string) bool {
	stack := map[int]int{}
	starStack := map[int]int{}
	starStackTop := -1
	stackTop := -1

	for i := range s {
		if s[i] == '(' {
			stackTop++
			stack[stackTop] = i
			continue
		} else if s[i] == '*' {
			starStackTop++
			starStack[starStackTop] = i
			continue
		} else if s[i] == ')' {
			if stackTop != -1 {
				delete(stack, stackTop)
				stackTop--
				continue
			} else if starStackTop != -1 {
				delete(starStack, starStackTop)
				starStackTop--
				continue
			} else {
				return false
			}
		} else {
			return false
		}
	}

	for stackTop != -1 && starStackTop != -1 {
		if stack[stackTop] > starStack[starStackTop] {

			return false
		}
		stackTop--
		starStackTop--
	}
	return stackTop == -1
}
